#include <list>
#include <vector>
#include <queue>

#include "cover.h"

using std::list;
using std::vector;

/**
 * Greedy algorithm based on SET COVER
 * Modifies: matrix, cover, solutions
 *
 * @param   matrix  the 0,1 matrix represented as vector of vectors of int
 * @param   ncols   number of data columns representing lines,
 *		    not number of characters
 * @param   nrows   number of rows
 * @param   cover   int array of length ncols
 * @param   solutions	a storage container for solution row indices
 */
void greedy_sc (
	vector<vector<int> > &matrix,
	int nrows,
	int ncols,
	int *cover,
	list<int> &solutions
	)
{
    /**
     * Algorithm description
     *
     * while not finished covering
     *. count the number of 1's in each row (rowsums)
     *. find the row with the greatest rowsum 
     *. add that row to the solution set
     *. cover matrix with that row
     */

    int *rowsums = new int[nrows];	// for greediness counting

    /* initialize rowsums: count the 1's in each row */
    int * row = rowsums;
    vector<vector<int> >::iterator rowvi = matrix.begin();
    vector<vector<int> >::iterator rowendi = matrix.end();
    vector<int>::iterator itr, end;
    while (rowvi != rowendi) {
	itr = rowvi->begin();
	end = rowvi->end();
	int count = 0;
	while ( itr != end ) {
	    count += *itr++;
	}
	*row = count;
	++row; ++rowvi;
    }

    int * const endrow = rowsums + nrows;
    int * maxrow = rowsums;
    while ( !finished(cover, ncols) ) {
	/* find max row */
	row = rowsums;
	while (row != endrow) {
	    if (*maxrow < *row) { maxrow = row; }
	    ++row;
	}

	int rowi = maxrow - rowsums;	    // get maxrow index
	solutions.push_back(rowi);	    // add maxrow to solution set
	// cover matrix with row rowi
	cover_with_row (matrix, rowi, cover, rowsums, NULL);
    }

    /* clean up duty -- free up memory */
    delete[] rowsums;
}

